#ifndef REMAINDER_H
#define REMAINDER_H

#include <cassert>

template<typename T>
T slow_remainder(T a, T b)
{
	while (b<=a)
		a = a - b;
	return a;
}

template<typename T>
T slow_quotient(T a, T b)
{
	T n(0);
	while (b <= a) {
		a = a - b;
		++n;
	}
	return n;
}

template<typename T>
T remainder_recursive(T a, T b)
{
	assert(a >=b);
	assert(b > 0);
	if (a - b >= b) {
		a = remainder_recursive(a, b + b);
		if (a < b) 
			return a;
	}
	return a - b;
}

template<typename T>
T remainder_nonnegative(T a, T b)
{
	assert(a >=0);
	assert(b > 0);
	if (a < b)
		return a;
	return remainder_recursive(a,b);
}

template<typename T>
T remainder_nonnegative_iterative(T a, T b)
{
	if (a < b) return a;
	T c = largest_doubling(a, b);
	a = a - c;
	while (c != b) {
		c = half(c);
		if (c <= a) 
			a = a - c;
	}
	return a;
}

template<typename T>
T largest_doubling(T a, T b)
{
	while (b <= a - b)
		b = b + b;
	return b;
}
template<typename T>
T half(T a)
{
	return a = a/2;
}

template<typename Op,typename T>
T remainder(T a, T b, Op rem)
{
	assert(b != 0);
	T r;
	if (a < T(0)) {
		if (b < T(0)) {
			r = -rem(-a,-b);
		}
		else {
			r = rem(-a,b);
			if (r != T(0))
				r = b - r;
		}
	}
	else { //a >= 0
		if (b < T(0)) {
			r = rem(a,-b); 
			if (r != T(0))
				r = b + r;
		}
		else {
			r = rem(a,b);
		}
	}
	return r;
}

#endif